package william.list;

import java.util.LinkedList;

/**
 * @author ZhangShenao
 * @date 2024/3/10
 * @description <a href="https://leetcode.cn/problems/add-two-numbers-ii/description/">...</a>
 */
public class Leetcode445_两数相加2 {
    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 借助栈实现
     * 首先遍历两个链表,将所有节点保存在栈中
     * 然后依次弹栈,将节点相加,压入结果栈
     * 最后遍历结果栈,组成结果链表
     * <p>
     * 时间复杂度O(N) 两个链表各遍历一遍,三个栈各遍历一遍
     * 空间复杂度O(N) 需要额外申请三个栈空间
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //边界条件校验
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        //申请两个栈,保存两个操作数链表
        LinkedList<Integer> stack1 = new LinkedList<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        LinkedList<Integer> stack2 = new LinkedList<>();
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }

        //申请结果栈
        LinkedList<Integer> result = new LinkedList<>();

        //遍历两个栈,将结果相加,保存在结果栈中
        int carry = 0;  //记录进位
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            //如果其中一个操作数栈为空,则补0
            int v1 = stack1.isEmpty() ? 0 : stack1.pop();
            int v2 = stack2.isEmpty() ? 0 : stack2.pop();
            int sum = v1 + v2 + carry;
            result.push(sum % 10);
            carry = sum / 10;
        }

        //处理最后的进位
        if (carry > 0) {
            result.push(carry);
        }

        //将结果栈组成链表返回
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (!result.isEmpty()) {
            cur.next = new ListNode(result.pop());
            cur = cur.next;
        }

        return dummy.next;
    }
}
